package com.chilly.other.datastructer;

import lombok.var;

/**
 * https://github.com/YUbuntu0109/YUbuntu0109.github.io/blob/a519387ae90ea45dc929c37c98eaf9624600b421/source/_posts/%E8%AF%A6%E8%A7%A3Binary-Tree%E7%9A%84%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8.md
 *
 * 分别测试二叉树的前序,中序,后序遍历方式
 * <p>
 * Created by Chilly Cui on 2021/1/7.
 */
public class BinaryTree {
    public static BinaryTreeNode initBinaryTree() {
        BinaryTreeNode root = new BinaryTreeNode();
        root.setData(1); //根节点
        root.setLeft(new BinaryTreeNode(2, new BinaryTreeNode(4), new BinaryTreeNode(5))); //左子树
        root.setRight(new BinaryTreeNode(3, new BinaryTreeNode(6), new BinaryTreeNode(7))); //右子树
        return root;
    }

    //递归前序遍历
    public void preOrder(BinaryTreeNode root) {
        if (root != null) {
            System.out.print(root.getData() + ", ");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    //非递归前序遍历
    public void preOrderNonRecursive(BinaryTreeNode root) {
        if (root == null) {
            System.err.println("error : the tree is empty");
        }
        var stack = new LLStack<BinaryTreeNode>();
        while (true) {
            while (root != null) {
                System.out.print(root.getData() + ", ");
                stack.push(root);
                root = root.getLeft();
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop();
            root = root.getRight();
        }
    }

    //递归中序遍历
    public void inOrder(BinaryTreeNode root) {
        if (root != null) {
            inOrder(root.getLeft());
            System.out.print(root.getData() + ", ");
            inOrder(root.getRight());
        }
    }

    //非递归中序遍历
    public void inOrderNonRecursive(BinaryTreeNode root) {
        if (root == null) {
            System.err.println("error : the tree is empty");
        }
        var stack = new LLStack<BinaryTreeNode>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.getLeft();
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop();
            System.out.print(root.getData() + ", ");
            root = root.getRight();
        }
    }

    //递归后序遍历
    public void postOrder(BinaryTreeNode root) {
        if (root != null) {
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getData() + ", ");
        }
    }

    //非递归后序遍历
    public void postNonRecursive(BinaryTreeNode root) {
        /*if (root == null) {
            System.err.println("error : the tree is empty");
        }
        var stack = new LLStack<BinaryTreeNode>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.getLeft();
            }
            if (stack.isEmpty()) {
                break;
            }
            root = stack.pop();
            root = root.getRight();
            System.out.print(root.getData() + ", ");
        }*/
    }

    //test
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTreeNode binaryTreeNode = BinaryTree.initBinaryTree();
        System.out.println("------ 递归前序遍历 ------");
        binaryTree.preOrder(binaryTreeNode); //1,2,4,5,3,6,7
        System.out.println("\n------ 非递归前序遍历 ------");
        binaryTree.preOrderNonRecursive(binaryTreeNode);
        System.out.println("\n------ 递归中序遍历 ------");
        binaryTree.inOrder(binaryTreeNode); //4,2,5,1,6,3,7
        System.out.println("\n------ 非递归中序遍历 ------");
        binaryTree.inOrderNonRecursive(binaryTreeNode);
        System.out.println("\n------ 递归后序遍历 ------");
        binaryTree.postOrder(binaryTreeNode); //4,5,2,6,7,3,1
        System.out.println("\n------ 非递归中序遍历 ------");
        binaryTree.postNonRecursive(binaryTreeNode); //4,5,2,6,7,3,1
    }
}
